package 剑指offer;

/**
 * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 * @author Administrator
 *
 */

public class 找出中序遍历顺序的下一个结点2 {
    
    public static void dispaly(TreeLinkNode tree) {
	if(tree!=null) {
	    	dispaly(tree.left);
		System.out.println(tree.val);
		dispaly(tree.right);//左根右

	}
}
    public static void main(String[] args) {
	// TODO Auto-generated method stub
		/*
		 * 	       8
		 * 	  6	    10
		 *    5      7   9	 11
		 * 
		 * 
		 */
	TreeLinkNode root=new TreeLinkNode(8);
	root.next = null;
	
	root.left=new TreeLinkNode(6);
	root.left.next =root;
	root.right=new TreeLinkNode(10);
	root.right.next =root;
	
	root.left.left=new TreeLinkNode(5);
	root.left.left.next = root.left;
	root.left.right=new TreeLinkNode(7);
	root.left.right.next = root.left;
	
	root.right.left=new TreeLinkNode(9);
	root.right.left.next = root.right;
	root.right.right=new TreeLinkNode(11);
	root.right.right.next = root.right;
	dispaly(root);
	System.out.println(GetNext(root.right).val);
	
    }
    public static TreeLinkNode GetNext(TreeLinkNode pNode)
    {
	if(pNode==null) {
	    return null;
	}
	TreeLinkNode currentNode = pNode;
	if(currentNode.right!=null) {
	    TreeLinkNode node =currentNode.right;
	    while (node.left!=null) {
		node = node.left;
	    }
	    return node;
	}
	while(currentNode.next!=null) {
	   currentNode = currentNode.next;
	   if(currentNode.left == pNode) {
	       return currentNode;
	   }else {
	       pNode = currentNode.next;
	   }
	}
	return null;
        
    }

}
